package leetcode.code1043;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int maxSumAfterPartitioning(int[] arr, int k) {
		int len = arr.length;
		Integer[][] dp = new Integer[len][len];
		int[][] maxs = new int[len][len];
		for (int i = 0; i < len; i++) {
			maxs[i][i] = arr[i];
		}
		// [0,len]
		for (int i = len - 1; i >= 0; i--) {
			for (int j = i + 1; j < maxs.length; j++) {
				maxs[i][j] = Math.max(maxs[i + 1][j], maxs[i][j - 1]);
			}
		}
		return this.f(arr, 0, len - 1, k, dp, maxs);
	}

	private int f(int[] arr, int L, int R, int k, Integer[][] dp, int[][] maxs) {
		if (L == R) {
			return arr[L];
		}
		if (dp[L][R] != null) {
			return dp[L][R];
		}
		int size = R - L + 1, ans = 0;
		if (size <= k) {
			ans = size * maxs[L][R];
		} else {
			for (int i = 0; i < k; i++) {
				ans = Math.max(ans, this.f(arr, L, L + i, k, dp, maxs) + this.f(arr, L + i + 1, R, k, dp, maxs));
//				ans = Math.max(ans, this.f(arr, L, R - i - 1, k, dp, maxs) + this.f(arr, R - i, R, k, dp, maxs));
			}
		}
		dp[L][R] = ans;
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(84, this.maxSumAfterPartitioning(H.str2array3("[1,15,7,9,2,5,10]"), 3));
		H.compare(83, this.maxSumAfterPartitioning(H.str2array3("[1,4,1,5,7,3,6,1,9,9,3]"), 4));
		H.compare(1, this.maxSumAfterPartitioning(H.str2array3("[1]"), 1));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
